package evaluation;

/**
 * 小和问题,归并排序的变形，一定要排序，时间复杂度为O（NLogN）
 */
public class SmallSum {

    //递归
    public static int process(int[] arr,int l, int r){
        if (l==r){
            return 0;
        }
        int mid = l + ((r-l) >>1);
        return process(arr,l,mid) + process(arr,mid+1,r) + merge(arr,l,mid,r);
    }

    private static int merge(int[] arr, int l, int mid, int r) {
        int help[] = new int[r-l+1];
        int i=0;
        int p1 = l;
        int p2 =mid + 1;
        int res = 0;
        //算出值
        while (p1 <= mid && p2<=r){
            res += arr[p1] <arr[p2] ? (r-p2+1) * arr[p1] :0;
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1<=mid){
            help[i++] = arr[p1++];
        }
        while (p2<=r){
            help[i++] = arr[p2++];
        }
        //排序
        for (int i2 = 0; i2 < help.length; i2++) {
            arr[l+i2] = help[i2];
        }
        //返回值
        return res;
    }

    public static void main(String[] args) {
        int[] arrs = {1,3,4,2,5};
        System.out.println(process(arrs,0,arrs.length-1));
    }
}
